package mid

import (
	"fmt"
	"workspace/node"
)

func AllPossibleFBT(n int) []*node.TreeNode {
	var fullBinaryTrees []*node.TreeNode
	if n%2 == 0 {
		return fullBinaryTrees
	}
	if n == 1 {
		fullBinaryTrees = append(fullBinaryTrees, &node.TreeNode{Val: 0})
		return fullBinaryTrees
	}
	for i := 1; i < n; i += 2 {
		leftSubtrees := AllPossibleFBT(i)
		rightSubtrees := AllPossibleFBT(n - 1 - i)
		for _, leftSubtree := range leftSubtrees {
			for _, rightSubtree := range rightSubtrees {
				root := &node.TreeNode{Val: 0, Left: leftSubtree, Right: rightSubtree}
				fullBinaryTrees = append(fullBinaryTrees, root)
			}
		}
	}
	return fullBinaryTrees
}
func PreOrderTraversal(root *node.TreeNode) {
	if root == nil {
		return
	}
	fmt.Print(root.Val, " ")
	PreOrderTraversal(root.Left)
	PreOrderTraversal(root.Right)
}
